W2. Элементарные матрицы, LU-разложение, pivoting, LDU и разложение Холецкого

1. Краткое содержание

1.1 Элементарные матрицы

Перед тем как переходить к элементарным матрицам, вспомним единичную матрицу (identity matrix) \(I\): квадратная, на главной диагонали единицы, вне её нули (например, \(I_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\)). При умножении любой матрицы \(A\) на \(I\) слева или справа получаем снова \(A\): \(IA = AI = A\).

Элементарная матрица (elementary matrix) получается одним элементарным преобразованием строк (elementary row operation) над единичной матрицей \(I\). Три таких преобразования:

1. Перестановка двух строк (swap)
2. Умножение строки на ненулевой скаляр (scaling)
3. Прибавление к одной строке другой, умноженной на скаляр (row addition)

Они лежат в основе исключения Гаусса (Gaussian elimination) — систематического приведения матрицы к ступенчатому / верхнетреугольному виду. Элементарные матрицы удобны тем, что каждый шаг приведения можно записать как умножение слева на элементарную матрицу.

Зачем это нужно: так мы алгебраически отслеживаем всю цепочку операций Гаусса и естественно приходим к факторизациям вроде LU-разложения (LU decomposition).

Три типа элементарных матриц соответствуют трём операциям:

• Перестановка строк (row swap) \(P_{ij}\): в \(I\) меняются местами строки \(i\) и \(j\); \(P_{ij}A\) делает то же с \(A\).
• Масштабирование строки (row scaling) \(D_i(\alpha)\): строка \(i\) в \(I\) умножается на \(\alpha \neq 0\); \(D_i(\alpha)A\) масштабирует строку \(i\) матрицы \(A\).
• Прибавление строки (row addition) \(E_{ij}(\alpha)\): к строке \(i\) в \(I\) прибавляется \(\alpha\) умноженная строка \(j\); \(E_{ij}(\alpha)A\) выполняет ту же операцию над \(A\).

1.1.1 Обратные к элементарным

Каждая элементарная матрица обратима; обратная снова элементарная и «отменяет» операцию:

• \(P_{ij}^{-1} = P_{ij}\) (двойная перестановка возвращает исходное)
• \(D_i(\alpha)^{-1} = D_i(1/\alpha)\) (обратное масштабирование)
• \(E_{ij}(\alpha)^{-1} = E_{ij}(-\alpha)\) (вычитаем то, что прибавили)

1.1.2 Определители элементарных матриц

• \(\det(P_{ij}) = -1\) (перестановка строк меняет знак)
• \(\det(D_i(\alpha)) = \alpha\)
• \(\det(E_{ij}(\alpha)) = 1\) (прибавление кратной строки не меняет \(\det\))

1.1.3 Базовый факт

Любая обратимая матрица — произведение элементарных: \[A = E_1 E_2 \cdots E_k\] Тогда \[A^{-1} = E_k^{-1} \cdots E_2^{-1} E_1^{-1}\]

Это теоретическая основа метода Гаусса–Жордана (Gauss–Jordan elimination): приведение \([A \mid I]\) к \([I \mid A^{-1}]\) — это последовательное умножение слева на элементарные матрицы.

1.2 Умножение справа на элементарные

Важное различие: при умножении слева \(EA\) выполняется строковая операция; при умножении справа \(AE\) — соответствующая столбцовая (с соглашением индексов для \(E_{ij}\), как в таблице).

Операция	Слева \(EA\)	Справа \(AE\)
Перестановка \(P_{ij}\)	Меняет строки \(i\) и \(j\)	Меняет столбцы \(i\) и \(j\)
Масштаб \(D_i(\alpha)\)	Масштабирует строку \(i\)	Масштабирует столбец \(i\)
Прибавление \(E_{ij}(\alpha)\)	К строке \(i\) \(+\alpha\)·(строка \(j\))	К столбцу \(j\) \(+\alpha\)·(столбец \(i\))
На что влияет	row space	column space
Сохраняет	связи между столбцами	связи между строками
Типичное применение	решение \(Ax = b\)	решение \(xA = b\)

Например, если \(A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}\) и \(P_{23} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}\), то \(P_{23}A\) переставляет строки 2 и 3, а \(AP_{23}\) — столбцы 2 и 3.

1.2.1 Свойства матриц перестановки

Матрица \(P_{ij}\) симметрична и ортогональна: \[P_{ij}^T = P_{ij}^{-1} = P_{ij}\] то есть совпадает со своей обратной и транспонированной.

Для симметричных матриц часто используют симметричные перестановки вида \(PAP^T\): одновременно переставляются строки и столбцы. Симметрия и структура спектра сохраняются, так как \((PAP^T)^T = (P^T)^T A^T P^T = PAP^T\).

1.3 Треугольные системы

Прежде чем обсуждать факторизации, важно понять, чем удобны треугольные системы. Матрица верхнетреугольная (upper triangular), если под главной диагональю нули (например, \(\begin{bmatrix} 2 & 3 & 4 \\ 0 & 5 & 6 \\ 0 & 0 & 7 \end{bmatrix}\)). Нижнетреугольная (lower triangular), если нули над диагональю (например, \(\begin{bmatrix} 2 & 0 & 0 \\ 3 & 5 & 0 \\ 4 & 6 & 7 \end{bmatrix}\)).

Почему это важно: для треугольной \(A\) система \(Ax = b\) решается прямой или обратной подстановкой за \(O(n^2)\) — существенно быстрее общего случая. Отсюда мотивация писать \(A = LU\) с нижней \(L\) и верхней \(U\): вместо одной «тяжёлой» системы получаем две треугольные.

1.3.1 Прямая подстановка (нижняя треугольная)

Для \(Lx = b\) неизвестные находят сверху вниз: первое уравнение содержит только \(x_1\), второе — \(x_1,x_2\) и т.д. Это прямая подстановка (forward substitution).

Пример: \(\begin{bmatrix} 2 & 0 & 0 \\ 3 & 5 & 0 \\ 4 & 6 & 7 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 10 \\ 22 \\ 45 \end{bmatrix}\):

• Сначала: \(2x_1 = 10 \implies x_1 = 5\)
• Затем: \(3x_1 + 5x_2 = 22 \implies 15 + 5x_2 = 22 \implies x_2 = 1{,}4\)
• Наконец: \(4x_1 + 6x_2 + 7x_3 = 45 \implies 20 + 8{,}4 + 7x_3 = 45 \implies x_3 = 2{,}37\ldots\)

Общая форма: \[x_1 = b_1 / l_{11}, \quad x_2 = (b_2 - l_{21}x_1) / l_{22}, \quad \ldots\]

Компактно: \[x_i = \frac{1}{l_{ii}} \left( b_i - \sum_{j=1}^{i-1} l_{ij} x_j \right)\]

1.3.2 Обратная подстановка (верхняя треугольная)

Для \(Ux = b\) идут снизу вверх: последнее уравнение даёт \(x_n\), предыдущее — \(x_{n-1},x_n\) и т.д. Это обратная подстановка (back substitution).

Пример: \(\begin{bmatrix} 2 & 3 & 4 \\ 0 & 5 & 6 \\ 0 & 0 & 7 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 20 \\ 23 \\ 14 \end{bmatrix}\):

• Снизу: \(7x_3 = 14 \implies x_3 = 2\)
• Выше: \(5x_2 + 6x_3 = 23 \implies 5x_2 + 12 = 23 \implies x_2 = 2{,}2\)
• Верх: \(2x_1 + 3x_2 + 4x_3 = 20 \implies 2x_1 + 6{,}6 + 8 = 20 \implies x_1 = 2{,}7\)

Общая форма: \[x_n = b_n / u_{nn}, \quad x_{n-1} = (b_{n-1} - u_{n-1,n}x_n) / u_{n-1,n-1}, \quad \ldots\]

Компактно: \[x_i = \frac{1}{u_{ii}} \left( b_i - \sum_{j=i+1}^{n} u_{ij} x_j \right)\]

1.4 LU-разложение

LU-разложение (LU decomposition / LU factorization) — одна из центральных факторизаций: \(A = LU\), где \(L\) нижняя треугольная, \(U\) верхняя треугольная: \[A = LU\]

Идея: вместо того чтобы каждый раз решать \(Ax = b\) полным исключением Гаусса (\(O(n^3)\)), один раз находим \(LU\), а затем для любого \(b\):

1. Решаем \(Ly = b\) (прямая подстановка),
2. Решаем \(Ux = y\) (обратная подстановка).

Так как \(A = LU\), положим \(y = Ux\), тогда \(LUx = b\) сводится к этим двум шагам.

Связь с Гауссом: \(U\) — то, что получается после исключения (ступенчатый / верхнетреугольный вид); в \(L\) записываются множители (multipliers) шагов исключения — числа, на которые умножают вычитаемую строку (например, при «строка 2 − 4·строка 1» множитель 4 попадает в позицию \(l_{21}\) в принятой конвенции курса).

Для единственности обычно требуют, чтобы \(L\) была нижней с единицами на диагонали (unit lower triangular): на диагонали \(L\) стоят 1.

1.4.1 Вывод LU из исключения Гаусса

Каждому шагу исключения соответствует элементарная матрица. Если \(E_k \cdots E_2 E_1 A = U\), то \[E_k \cdots E_2 E_1 A = U\] \[A = E_1^{-1} E_2^{-1} \cdots E_k^{-1} U = LU\]

Произведение \(L = E_1^{-1} E_2^{-1} \cdots E_k^{-1}\) нижнетреугольно; поддиагональные элементы \(L\) связаны с множителями исключения (часто — со знаком по конвенции: если из строки 2 вычитают 4·строку 1, в \(L\) может стоять \(l_{21} = 4\)).

1.4.2 Существование и единственность

Обратимая \(A\) допускает классическое \(LU\) без перестановок тогда и только тогда, когда все ведущие главные миноры (leading principal minors) ненулевы.

Что такое \(M_k\)? Это \(\det\) левого верхнего блока \(k \times k\). Для \(3 \times 3\):

• \(M_1 = a_{11}\)
• \(M_2 = \det\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix}\)
• \(M_3 = \det(A)\)

Если \(M_k = 0\), на \(k\)-м шаге pivot обнуляется — стандартное \(LU\) без перестановок ломается, нужен pivoting (перестановки строк).

Если \(A\) обратима и все \(M_k \neq 0\), то \(LU\) с unit нижней \(L\) единственно.

Пример отсутствия \(LU\): \(\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) обратима, но \(M_1 = 0\) — без перестановок \(LU\) нет.

1.4.3 Почему LU выгодно

Если решать \(Ax = b\) для многих \(b_1,\ldots,b_k\), наивный Гаусс каждый раз стоит \(k \cdot \frac{2}{3}n^3\) flops. С \(LU\): один раз \(\frac{2}{3}n^3\) на факторизацию и по \(2n^2\) на каждую систему — всего \(\frac{2}{3}n^3 + k \cdot 2n^2\); при большом \(k\) выигрыш огромен.

Численный пример: при \(n = 1000\) и \(1000\) правых частей — порядка 2{,}67·\(10^9\) flops против ~667·\(10^9\) при повторном полном исключении.

1.5 Выбор главного элемента (pivoting)

При исключении Гаусса двигаемся по диагонали, используя диагональный ведущий элемент (pivot) для обнуления поддиагонали. Если pivot нулевой — делить нельзя; если он очень мал, деление усиливает ошибки округления в численной арифметике с плавающей точкой.

Решение — pivoting: переставляем строки (а при полном pivoting — и столбцы), чтобы в позицию pivot попал более крупный по модулю элемент. Это нужно и для корректности, и для численной устойчивости (numerical stability).

Что такое устойчивость: в точной арифметике мелкие погрешности не видны; на машине они накапливаются. Устойчивый алгоритм не даёт им «взрываться»; pivoting уменьшает риск деления на малые pivot.

1.5.1 Частичный выбор (partial pivoting)

Partial pivoting: в текущем столбце ниже диагонали ищут элемент максимальной по модулю величины и переставляют его в pivot-позицию.

Алгоритм на шаге \(k\):

1. Найти \(p\) с \(|a_{pk}| = \max_{i \ge k} |a_{ik}|\)
2. Поменять местами строки \(k\) и \(p\)
3. Продолжить исключение

Получаем \[PA = LU\] где \(P\) — произведение перестановок строк, \(L\) — unit нижняя с \(|l_{ij}| \le 1\), \(U\) — верхняя.

Для любой обратимой \(A\) partial pivoting возможен; при фиксированном \(P\) пары \(L,U\) единственны.

1.5.2 Полный выбор (complete pivoting)

Complete pivoting: в оставшейся подматрице ищут максимум по модулю среди всех позиций \(i,j \ge k\).

Алгоритм на шаге \(k\):

1. Найти \((p,q)\) с \(|a_{pq}| = \max_{i,j \ge k} |a_{ij}|\)
2. Переставить строки \(k\) и \(p\) (матрица \(P\))
3. Переставить столбцы \(k\) и \(q\) (матрица \(Q\))
4. Продолжить исключение

Итог: \[PAQ = LU\] существует для любой \(A\), в том числе вырожденной.

1.5.3 Численная устойчивость и рост элементов

Фактор роста (growth factor) \(\rho\) показывает, насколько выросли элементы при исключении: \[\rho = \frac{\max_{i,j} |a_{ij}^{(k)}|}{\max_{i,j} |a_{ij}|}\]

• Без pivoting: \(\rho\) может достигать \(2^{n-1}\) (катастрофа)
• Partial: в худшем случае \(\rho \le 2^{n-1}\), на практике обычно мало
• Complete: оценка вида \(\rho \le n^{1/2}(2 \cdot 3^{1/2} \cdots n^{1/(n-1)}) \sim O(n^{\frac{1}{2}\log n})\)

	Partial	Complete
Операция	Перестановки строк	Строки + столбцы
Поиск за шаг	\(O(n)\)	\(O(n^2)\)
Доп. стоимость всего	\(O(n^2)\)	\(O(n^3)\)
Устойчивость	Обычно достаточно	Наилучшая оценка роста
Граница роста	\(\le 2^{n-1}\)	\(\sim O(n^{\log n})\)
Вид	\(PA = LU\)	\(PAQ = LU\)
Когда	По умолчанию	Плохо обусловленные / неполный ранг

1.5.4 Rook pivoting

Rook pivoting — компромисс: просматривают текущую строку и столбец и останавливаются на первом элементе, который одновременно максимален в своей строке и столбце. Ожидаемая стоимость поиска \(O(n^2)\), устойчивость близка к complete.

1.5.5 Решение систем при complete pivoting

Для \(AX = B\):

1. Найти \(PAQ = LU\)
2. Записать \(PAQ(Q^TX) = PB\)
3. Положить \(Y = Q^TX\), решить \(LZ = PB\) (прямая подстановка), затем \(UY = Z\) (обратная)
4. Восстановить \(X = QY\)

1.5.6 Определитель при pivoting

Для перестановки \(P_{ij}\):

• \(\det(P_{ij}A) = -\det(A)\) (перестановка строк)
• \(\det(AP_{ij}) = -\det(A)\) (перестановка столбцов)
• \(\det(P_{ij}AP_{ij}) = \det(A)\) (одновременно строки и столбцы)

Из \(PAQ = LU\): \[\det(A) = \det(P^{-1}) \det(L) \det(U) \det(Q^{-1}) = \pm \prod_{i} u_{ii}\]

1.5.7 Когда что использовать

Partial pivoting достаточно для:

• большинства хорошо обусловленных задач;
• диагонально доминирующих матриц;
• SPD-матриц (часто pivoting не нужен).

Complete pivoting полезен при:

• плохой обусловленности (ill-conditioned): малые возмущения входа сильно меняют решение; число обусловленности \(\kappa(A) \gg 1\);
• матрицах неполного ранга (rank-deficient);
• поиске ядра (null space): все \(x\) с \(Ax = 0\);
• задачах, где критична обратная устойчивость (backward stability).

1.6 LDU-разложение

Из \(A = LU\) можно вынести диагональ из \(U\): \[A = LDU_0\] где

• \(D = \text{diag}(u_{11}, u_{22}, \ldots, u_{nn})\) — диагональная матрица pivot из \(U\);
• \(U_0 = D^{-1}U\) — верхняя с единицами на диагонали (unit upper triangular).

Так проще видеть роль pivot и переходить к \(LDL^T\) для симметричных матриц.

1.6.1 Симметричный случай \(LDL^T\)

Если \(A = A^T\), в LDU-форме \(U_0 = L^T\): \[A = LDL^T\] Экономнее по памяти (храним \(L\) и \(D\)) и сохраняет симметрию.

1.7 Симметричные положительно определённые матрицы и Холецкий

\(A\) симметрична, если \(A = A^T\) (\(a_{ij} = a_{ji}\)). Симметричные матрицы часто встречаются в физике, оптимизации и статистике.

\(A\) симметрична положительно определённа (SPD), если \(x^TAx > 0\) для всех \(x \neq 0\).

Выражение \(x^TAx\) — квадратичная форма (quadratic form). Для SPD она положительна вне нуля; геометрически — «чаша» без седловых точек. У SPD положительные собственные значения, они обратимы, методы обычно устойчивы.

1.7.1 Критерий Сильвестра

Sylvester’s criterion: симметричная \(A\) положительно определена тогда и только тогда, когда все ведущие главные миноры положительны: \(M_1 > 0,\ldots,M_n > 0\). Это сводит проверку к \(n\) определителям вместо «бесконечного» перебора \(x\).

1.7.2 Разложение Холецкого

Для SPD в \(LDL^T\) все \(d_i > 0\), поэтому \(d_i = (\sqrt{d_i})^2\) и \(D = D^{1/2}D^{1/2}\). Поглощая корни в \(L\), получают \[A = L D L^T = (LD^{1/2})(LD^{1/2})^T\]

Обычно пишут \(A = LL^T\), где \(L\) нижняя с положительной диагональю — это разложение Холецкого (Cholesky decomposition).

Плюсы: \(\frac{1}{3}n^3\) flops (примерно вдвое дешевле LU), устойчивость без pivoting, один треугольный множитель.

1.8 Обращение матрицы

Обратная \(A^{-1}\) удовлетворяет \(AA^{-1} = A^{-1}A = I\). Существует только для обратимых (nonsingular) матриц; критерий: \(\det A \neq 0\).

Теоретически \(x = A^{-1}b\), но на практике \(A^{-1}\) редко считают явно — дорого и менее устойчиво; предпочитают \(LU\) и т.п.

1.8.1 Формула \(2 \times 2\)

Если \(A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}\) и \(ad - bc \neq 0\): \[A^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\]

Мнемоника: поменять диагональ местами, поменять знак внедиагонали, разделить на \(\det A\).

1.8.2 Метод Гаусса–Жордана

Расширенная матрица \([A \mid I]\) строковыми операциями приводится к \([I \mid A^{-1}]\) — это тот же процесс, что умножение слева на \(E_k\cdots E_1 = A^{-1}\).

1.8.3 Свойства, сохраняемые при обращении

Если \(A\) обратима, то \(A^{-1}\):

• треугольна того же типа, что и \(A\);
• симметрична, если симметрична \(A\), так как \((A^{-1})^T = (A^T)^{-1}\);
• не обязана быть трёхдиагональной, даже если \(A\) трёхдиагональна;
• не обязана иметь целые элементы при целых \(A\).

1.9 Умножение матриц: строки и столбцы

Помимо стандартного «скалярное произведение строки на столбец», полезна картина линейных комбинаций.

По строкам: \(i\)-я строка \(AB\) — комбинация строк \(B\) с коэффициентами из \(i\)-й строки \(A\): \[\text{row}_i(AB) = a_{i1} \cdot \text{row}_1(B) + a_{i2} \cdot \text{row}_2(B) + \cdots + a_{in} \cdot \text{row}_n(B)\]

По столбцам: \(j\)-й столбец \(AB\) — комбинация столбцов \(A\) с коэффициентами из \(j\)-го столбца \(B\): \[\text{col}_j(AB) = b_{1j} \cdot \text{col}_1(A) + b_{2j} \cdot \text{col}_2(A) + \cdots + b_{nj} \cdot \text{col}_n(A)\]

Пример: для \(A = \begin{bmatrix} 2 & 1 & 4 \\ 0 & -1 & 1 \end{bmatrix}\) и \(B = \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{bmatrix}\) первая строка \(AB\): \[2 \cdot [1,1] + 1 \cdot [0,1] + 4 \cdot [1,0] = [6,3]\]

Отсюда ясно, почему слева от \(A\) меняются строки, справа — столбцы.

---

2. Определения

• Элементарная матрица (elementary matrix): один элементарный шаг строк над \(I\).
• Матрица перестановки строк \(P_{ij}\) (row swap / permutation matrix): меняет строки \(i\) и \(j\).
• Матрица масштабирования \(D_i(\alpha)\) (row scaling): умножает строку \(i\) на \(\alpha \neq 0\).
• Матрица прибавления строки \(E_{ij}(\alpha)\) (row addition): к строке \(i\) прибавляет \(\alpha\)·(строка \(j\)).
• LU-разложение: \(A = LU\), \(L\) — unit lower triangular, \(U\) — верхняя.
• Ведущий главный минор \(M_k\) (leading principal minor): \(\det\) левого верхнего блока \(k \times k\).
• Частичный выбор ведущего элемента (partial pivoting): перестановки строк, чтобы в позицию pivot попал максимальный по модулю элемент столбца; \(PA = LU\).
• Полный выбор ведущего элемента (complete pivoting): перестановки строк и столбцов; \(PAQ = LU\).
• «Ладейный» выбор pivot (rook pivoting): поиск в текущей строке и столбце.
• Фактор роста \(\rho\) (growth factor): отношение максимального элемента в процессе исключения к максимуму в \(A\).
• LDU-разложение: \(A = LDU_0\), \(D\) диагональна из pivot, \(U_0\) — unit upper.
• SPD-матрица: \(A = A^T\) и \(x^TAx > 0\) при \(x \neq 0\).
• Критерий Сильвестра (Sylvester’s criterion): \(A\) SPD \(\Leftrightarrow\) все \(M_k > 0\).
• Разложение Холецкого (Cholesky): для SPD, \(A = LL^T\), \(L\) нижняя с положительной диагональю.
• Эквивалентность матриц (matrix equivalence): \(B = PAQ\) для обратимых \(P,Q\).
• Исключение Гаусса–Жордана (Gauss–Jordan elimination): \([A \mid I] \to [I \mid A^{-1}]\).

---

3. Формулы

• Обратная к перестановке строк: \(P_{ij}^{-1} = P_{ij}\)
• Обратная к масштабу строки: \(D_i(\alpha)^{-1} = D_i(1/\alpha)\)
• Обратная к прибавлению строки: \(E_{ij}(\alpha)^{-1} = E_{ij}(-\alpha)\)
• \(\det\) перестановки строк: \(\det(P_{ij}) = -1\)
• \(\det\) масштаба строки: \(\det(D_i(\alpha)) = \alpha\)
• \(\det\) прибавления строки: \(\det(E_{ij}(\alpha)) = 1\)
• LU: \(A = LU\) (при \(M_k \neq 0\) для всех \(k\))
• LU + partial pivoting: \(PA = LU\) (для обратимой \(A\))
• LU + complete pivoting: \(PAQ = LU\) (для любой \(A\), в т.ч. вырожденной)
• LDU: \(A = LDU_0\), \(D = \text{diag}(u_{11}, \ldots, u_{nn})\), \(U_0 = D^{-1}U\)
• Симметричный LDU: \(A = LDL^T\)
• Холецкий: \(A = LL^T\) для SPD
• Стоимость Холецкого: \(\frac{1}{3}n^3\) flops
• Стоимость LU: \(\frac{2}{3}n^3\) на факторизацию, \(2n^2\) на одно решение
• Прямая подстановка (forward substitution): \(x_i = \frac{1}{l_{ii}}\left(b_i - \sum_{j=1}^{i-1} l_{ij}x_j\right)\)
• Обратная подстановка (back substitution): \(x_i = \frac{1}{u_{ii}}\left(b_i - \sum_{j=i+1}^{n} u_{ij}x_j\right)\)
• \(\det A\) из \(PAQ = LU\): \(\det(A) = \pm \prod_{i} u_{ii}\)
• Обратная \(2 \times 2\): \(\begin{bmatrix} a & b \\ c & d \end{bmatrix}^{-1} = \frac{1}{ad-bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\)
• Транспонирование и обращение: \((A^{-1})^T = (A^T)^{-1}\)
• Обратимая как произведение элементарных: \(A = E_1 E_2 \cdots E_k\)

---

4. Примеры

4.1. Обратная матрица с помощью матриц перестановок (Лаба 2, Задание 1)

Для данной матрицы A найдите обратную с помощью матриц перестановок. \[ \mathbf{A} = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 3 \\ 0 & 1 & 0 \end{bmatrix} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Приведите матрицу к диагональному виду. \[ \underbrace{\begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 3 \\ 0 & 1 & 0 \end{bmatrix}}_{\mathbf{A}} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}}_{\mathbf{P}} = \underbrace{\begin{bmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{\mathbf{D}} \] \[ \mathbf{A}\mathbf{P}\mathbf{P}^{-1} = \mathbf{D}\mathbf{P}^{-1} \quad \Rightarrow \quad \mathbf{A} = \mathbf{D}\mathbf{P}^{-1} \]

Шаг 2. Перейдите к обратной матрице. \[ \mathbf{A} = \mathbf{D}\mathbf{P}^{-1} \quad \Rightarrow \quad \mathbf{A}^{-1} = \left(\mathbf{D}\mathbf{P}^{-1}\right)^{-1} \quad \Rightarrow \quad \mathbf{A}^{-1} = \mathbf{P}\mathbf{D}^{-1} \]

\[ \underbrace{\begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 3 \\ 0 & 1 & 0 \end{bmatrix}^{-1}}_{\mathbf{A}^{-1}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}}_{\mathbf{P}} \underbrace{\begin{bmatrix} \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{3} & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{\mathbf{D}^{-1}} = \underbrace{\begin{bmatrix} \frac{1}{2} & 0 & 0 \\ 0 & 0 & 1 \\ 0 & \frac{1}{3} & 0 \end{bmatrix}}_{\mathbf{A}^{-1}} \]

Ответ: \(\mathbf{A}^{-1} = \begin{bmatrix} \frac{1}{2} & 0 & 0 \\ 0 & 0 & 1 \\ 0 & \frac{1}{3} & 0 \end{bmatrix}\)

4.2. Исключение Гаусса и LU-факторизация (Лаба 2, Задание 2)

Покажем эквивалентность исключения Гаусса и матричной факторизации. \[ \mathbf{A} = \begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Найдите верхнетреугольную матрицу методом Гаусса. \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} \xrightarrow{r_2 - 2r_1} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}^\star} \xrightarrow{r_3 + 1r_1} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 3 & 2 \end{bmatrix}}_{\mathbf{A}^{\star\star}} \]

\[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 3 & 2 \end{bmatrix}}_{\mathbf{A}^{\star\star}} \xrightarrow{r_3 + 3r_2} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \]

Шаг 2. Найдите верхнетреугольную матрицу через элементарные матрицы. \[ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{\mathbf{E_{21}}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}^\star} \]

\[ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}}_{\mathbf{E_{31}}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}^\star} = \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 3 & 2 \end{bmatrix}}_{\mathbf{A}^{\star\star}} \]

\[ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 3 & 1 \end{bmatrix}}_{\mathbf{E_{32}}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 3 & 2 \end{bmatrix}}_{\mathbf{A}^{\star\star}} = \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \]

Шаг 3. Соберите \(L\). \[ \mathbf{E}\mathbf{A} = \mathbf{U} \quad \Rightarrow \quad \mathbf{A} = \mathbf{E}^{-1}\mathbf{U} = \mathbf{L}\mathbf{U} \]

здесь \(\mathbf{L} = \mathbf{E}^{-1} = \mathbf{E}_{21}^{-1}\mathbf{E}_{31}^{-1}\mathbf{E}_{32}^{-1}\)

\[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \]

Ответ: \(A = LU\), где \(L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}\), \(U = \begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}\)

4.3. Решение СЛАУ через LU и прямую/обратную подстановку (Лаба 2, Задание 3)

Решите матричное уравнение с помощью LU-разложения и прямой/обратной подстановки. \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}}_{\mathbf{x}} = \underbrace{\begin{bmatrix} 3 \\ 3 \\ -2 \end{bmatrix}}_{\mathbf{b}} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Используйте LU-разложение. \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \]

\[ \underbrace{\mathbf{L}\mathbf{U}}_{\mathbf{A}} \mathbf{x} = \mathbf{b} \quad \Rightarrow \quad \mathbf{L} \underbrace{\mathbf{U}\mathbf{x}}_{\mathbf{y}} = \mathbf{b} \quad \Rightarrow \quad \mathbf{L}\mathbf{y} = \mathbf{b} \quad \Rightarrow \quad \mathbf{U}\mathbf{x} = \mathbf{y} \]

Шаг 2. Решите \(\mathbf{Ly} = \mathbf{b}\) относительно \(\mathbf{y}\) прямой подстановкой. \[ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix}}_{\mathbf{y}} = \underbrace{\begin{bmatrix} 3 \\ 3 \\ -2 \end{bmatrix}}_{\mathbf{b}} \]

\(y_1 = \frac{3}{1} = 3\)

\(y_2 = \frac{3 - 2 \cdot 3}{1} = -3\)

\(y_3 = \frac{-2 - (-1)(3) - (-3)(-3)}{1} = -8\)

Шаг 3. Решите \(\mathbf{Ux} = \mathbf{y}\) относительно \(\mathbf{x}\) обратной подстановкой. \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}}_{\mathbf{x}} = \underbrace{\begin{bmatrix} 3 \\ -3 \\ -8 \end{bmatrix}}_{\mathbf{y}} \]

\(x_3 = \frac{-8}{-4} = 2\)

\(x_2 = \frac{-3 - (-2)(2)}{-1} = -1\)

\(x_1 = \frac{3 - 1(2) - 1(-1)}{2} = 1\)

Ответ: \(\mathbf{x} = \begin{bmatrix} 1 \\ -1 \\ 2 \end{bmatrix}\)

4.4. LDU-разложение (Лаба 2, Задание 4)

Даны матрицы: \[ \mathbf{A} = \begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \]

Найдите LDU-разложение.

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Вынесите диагональ из \(U\). \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} = \underbrace{\begin{bmatrix} 2 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{D}} \underbrace{\begin{bmatrix} 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix}}_{\mathbf{U^\star}} \]

Шаг 2. Запишите LDU-факторизацию. \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} 2 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{D}} \underbrace{\begin{bmatrix} 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix}}_{\mathbf{U^\star}} \]

Ответ: \(A = LDU\), где \(L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}\), \(D = \begin{bmatrix} 2 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -4 \end{bmatrix}\), \(U = \begin{bmatrix} 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix}\)

4.5. Разложение Холецкого для симметричной положительно определённой матрицы (Лаба 2, Задание 5)

\[ \mathbf{A} = \begin{bmatrix} 1 & -2 & -1 \\ -2 & 8 & 4 \\ -1 & 4 & 11 \end{bmatrix} \]

Найдите разложение Холецкого \(A = LL^T\).

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Запишите схему разложения в символическом виде. \[ \underbrace{\begin{bmatrix} 1 & -2 & -1 \\ -2 & 8 & 4 \\ -1 & 4 & 11 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} l_{11} & l_{21} & l_{31} \\ 0 & l_{22} & l_{32} \\ 0 & 0 & l_{33} \end{bmatrix}}_{\mathbf{L^\text{T}}} \]

Шаг 2. Подставьте численные значения.

\(l_{11}^2 = 1 \Rightarrow l_{11} = 1\)

\(l_{11} \cdot l_{21} = -2 \Rightarrow l_{21} = -2\)

\(l_{11} \cdot l_{31} = -1 \Rightarrow l_{31} = -1\)

\(l_{21}^2 + l_{22}^2 = 8 \Rightarrow l_{22} = \sqrt{8 - 4} = 2\)

\(l_{21} \cdot l_{31} + l_{22} \cdot l_{32} = 4 \Rightarrow l_{32} = \frac{4 - 2}{2} = 1\)

\(l_{31}^2 + l_{32}^2 + l_{33}^2 = 11 \Rightarrow l_{33} = \sqrt{11 - 1 - 1} = 3\)

Шаг 3. Запишите \(L\) и \(L^T\). \[ \mathbf{L} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 2 & 0 \\ -1 & 1 & 3 \end{bmatrix}, \quad \mathbf{L}^\text{T} = \begin{bmatrix} 1 & -2 & -1 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \end{bmatrix} \]

Ответ: \(\mathbf{A} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 2 & 0 \\ -1 & 1 & 3 \end{bmatrix} \begin{bmatrix} 1 & -2 & -1 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \end{bmatrix}\)

4.6. Решение системы с разложением Холецкого (Лаба 2, Задание 6)

Решите уравнение для симметричной положительно определённой матрицы \(\mathbf{A}\): \[ \underbrace{\begin{bmatrix} 1 & -2 & -1 \\ -2 & 8 & 4 \\ -1 & 4 & 11 \end{bmatrix}}_{\mathbf{A}} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}}_{\mathbf{x}} = \underbrace{\begin{bmatrix} 3 \\ -8 \\ 5 \end{bmatrix}}_{\mathbf{b}} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Используйте разложение Холецкого \(LL^T\). \[ \underbrace{\begin{bmatrix} 1 & -2 & -1 \\ -2 & 8 & 4 \\ -1 & 4 & 11 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 2 & 0 \\ -1 & 1 & 3 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} 1 & -2 & -1 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \end{bmatrix}}_{\mathbf{L^\text{T}}} \]

\[ \underbrace{\mathbf{LL}^\text{T}}_{\mathbf{A}}\mathbf{x} = \mathbf{b} \quad \Rightarrow \quad \mathbf{L}\underbrace{\mathbf{L}^\text{T}\mathbf{x}}_{\mathbf{y}} = \mathbf{b} \]

Шаг 2. Решите \(\mathbf{Ly} = \mathbf{b}\) относительно \(\mathbf{y}\) прямой подстановкой. \[ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 2 & 0 \\ -1 & 1 & 3 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix}}_{\mathbf{y}} = \underbrace{\begin{bmatrix} 3 \\ -8 \\ 5 \end{bmatrix}}_{\mathbf{b}} \]

\(y_1 = 3\)

\(y_2 = \frac{-8 + 2 \cdot 3}{2} = -1\)

\(y_3 = \frac{5 + 1 \cdot 3 - 1 \cdot (-1)}{3} = 3\)

Шаг 3. Решите \(\mathbf{L}^\text{T}\mathbf{x} = \mathbf{y}\) относительно \(\mathbf{x}\) обратной подстановкой. \[ \underbrace{\begin{bmatrix} 1 & -2 & -1 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \end{bmatrix}}_{\mathbf{L^\text{T}}} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}}_{\mathbf{x}} = \underbrace{\begin{bmatrix} 3 \\ -1 \\ 3 \end{bmatrix}}_{\mathbf{y}} \]

\(x_3 = \frac{3}{3} = 1\)

\(x_2 = \frac{-1 - 1 \cdot 1}{2} = -1\)

\(x_1 = \frac{3 + 2 \cdot (-1) - (-1)(1)}{1} = 2\)

Ответ: \(\mathbf{x} = \begin{bmatrix} 2 \\ -1 \\ 1 \end{bmatrix}\)

4.7. Решение систем с заданной LU-факторизацией (часть 1) (Домашнее задание 2, Задание 1)

Решите \(A\mathbf{x} = \mathbf{b}\), используя данное LU-разложение \(A\): \[ A = \begin{bmatrix} 3 & -7 & -2 \\ -3 & 5 & 1 \\ 6 & -4 & 0 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} -7 \\ 5 \\ 2 \end{bmatrix} \] \[ A = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{bmatrix} \begin{bmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{bmatrix} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Укажите \(L\) и \(U\) из данной факторизации. \[L = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{bmatrix}\]

Шаг 2. Решите \(L\mathbf{y} = \mathbf{b}\) прямой подстановкой. \[\begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} -7 \\ 5 \\ 2 \end{bmatrix}\]

\(y_1 = -7\)

\(y_2 = 5 - (-1)(-7) = -2\)

\(y_3 = 2 - 2(-7) - (-5)(-2) = 2 + 14 - 10 = 6\)

Шаг 3. Решите \(U\mathbf{x} = \mathbf{y}\) обратной подстановкой. \[\begin{bmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} -7 \\ -2 \\ 6 \end{bmatrix}\]

\(x_3 = \frac{6}{-1} = -6\)

\(x_2 = \frac{-2 - (-1)(-6)}{-2} = \frac{-8}{-2} = 4\)

\(x_1 = \frac{-7 - (-7)(4) - (-2)(-6)}{3} = \frac{-7 + 28 - 12}{3} = \frac{9}{3} = 3\)

Ответ: \(\mathbf{x} = \begin{bmatrix} 3 \\ 4 \\ -6 \end{bmatrix}\)

4.8. Решение систем с заданной LU-факторизацией (часть 2) (Домашнее задание 2, Задание 2)

Решите \(A\mathbf{x} = \mathbf{b}\), используя данное LU-разложение \(A\): \[ A = \begin{bmatrix} 2 & -6 & 4 \\ -4 & 8 & 0 \\ 0 & -4 & 6 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 2 \\ -4 \\ 6 \end{bmatrix} \] \[ A = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2 & -6 & 4 \\ 0 & -4 & 8 \\ 0 & 0 & -2 \end{bmatrix} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Решите \(L\mathbf{y} = \mathbf{b}\) прямой подстановкой. \[\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 2 \\ -4 \\ 6 \end{bmatrix}\]

\(y_1 = 2\)

\(y_2 = -4 - (-2)(2) = 0\)

\(y_3 = 6 - 0 - 1(0) = 6\)

Шаг 2. Решите \(U\mathbf{x} = \mathbf{y}\) обратной подстановкой. \[\begin{bmatrix} 2 & -6 & 4 \\ 0 & -4 & 8 \\ 0 & 0 & -2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \\ 6 \end{bmatrix}\]

\(x_3 = \frac{6}{-2} = -3\)

\(x_2 = \frac{0 - 8(-3)}{-4} = \frac{24}{-4} = -6\)

\(x_1 = \frac{2 - (-6)(-6) - 4(-3)}{2} = \frac{2 - 36 + 12}{2} = \frac{-22}{2} = -11\)

Ответ: \(\mathbf{x} = \begin{bmatrix} -11 \\ -6 \\ -3 \end{bmatrix}\)

4.9. Решение систем с заданной LU-факторизацией (часть 3) (Домашнее задание 2, Задание 3)

Решите \(A\mathbf{x} = \mathbf{b}\), используя данное LU-разложение \(A\): \[ A = \begin{bmatrix} 2 & -4 & 2 \\ -4 & 5 & 2 \\ 6 & -9 & 1 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 6 \\ 0 \\ 6 \end{bmatrix} \] \[ A = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & -1 & 1 \end{bmatrix} \begin{bmatrix} 2 & -4 & 2 \\ 0 & -3 & 6 \\ 0 & 0 & 1 \end{bmatrix} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Решите \(L\mathbf{y} = \mathbf{b}\) прямой подстановкой. \[\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & -1 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 6 \\ 0 \\ 6 \end{bmatrix}\]

\(y_1 = 6\)

\(y_2 = 0 - (-2)(6) = 12\)

\(y_3 = 6 - 3(6) - (-1)(12) = 6 - 18 + 12 = 0\)

Шаг 2. Решите \(U\mathbf{x} = \mathbf{y}\) обратной подстановкой. \[\begin{bmatrix} 2 & -4 & 2 \\ 0 & -3 & 6 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 6 \\ 12 \\ 0 \end{bmatrix}\]

\(x_3 = \frac{0}{1} = 0\)

\(x_2 = \frac{12 - 6(0)}{-3} = -4\)

\(x_1 = \frac{6 - (-4)(-4) - 2(0)}{2} = \frac{6 - 16}{2} = -5\)

Ответ: \(\mathbf{x} = \begin{bmatrix} -5 \\ -4 \\ 0 \end{bmatrix}\)

4.10. Решение систем с заданной LU-факторизацией (часть 4) (Домашнее задание 2, Задание 4)

Решите \(A\mathbf{x} = \mathbf{b}\), используя данное LU-разложение \(A\): \[ A = \begin{bmatrix} 1 & -1 & 2 \\ 1 & -3 & 1 \\ 3 & 7 & 5 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 0 \\ -5 \\ 7 \end{bmatrix} \] \[ A = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 3 & -5 & 1 \end{bmatrix} \begin{bmatrix} 1 & -1 & 2 \\ 0 & -2 & -1 \\ 0 & 0 & -6 \end{bmatrix} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Решите \(L\mathbf{y} = \mathbf{b}\) прямой подстановкой. \[\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 3 & -5 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 0 \\ -5 \\ 7 \end{bmatrix}\]

\(y_1 = 0\)

\(y_2 = -5 - 1(0) = -5\)

\(y_3 = 7 - 3(0) - (-5)(-5) = 7 - 25 = -18\)

Шаг 2. Решите \(U\mathbf{x} = \mathbf{y}\) обратной подстановкой. \[\begin{bmatrix} 1 & -1 & 2 \\ 0 & -2 & -1 \\ 0 & 0 & -6 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 0 \\ -5 \\ -18 \end{bmatrix}\]

\(x_3 = \frac{-18}{-6} = 3\)

\(x_2 = \frac{-5 - (-1)(3)}{-2} = \frac{-2}{-2} = 1\)

\(x_1 = \frac{0 - (-1)(1) - 2(3)}{1} = \frac{0 + 1 - 6}{1} = -5\)

Ответ: \(\mathbf{x} = \begin{bmatrix} -5 \\ 1 \\ 3 \end{bmatrix}\)

4.11. Решение систем с заданной LU-факторизацией (часть 5) (Домашнее задание 2, Задание 5)

Решите \(A\mathbf{x} = \mathbf{b}\), используя данное LU-разложение \(A\): \[ A = \begin{bmatrix} 1 & -2 & -2 & -3 \\ 3 & -9 & 0 & -9 \\ -1 & 2 & 4 & 7 \\ -3 & -6 & 26 & 2 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 1 \\ 6 \\ 0 \\ 3 \end{bmatrix} \] \[ A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -3 & 4 & -2 & 1 \end{bmatrix} \begin{bmatrix} 1 & -2 & -2 & -3 \\ 0 & -3 & 6 & 0 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Решите \(L\mathbf{y} = \mathbf{b}\) прямой подстановкой. \[\begin{bmatrix} 1 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -3 & 4 & -2 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \end{bmatrix} = \begin{bmatrix} 1 \\ 6 \\ 0 \\ 3 \end{bmatrix}\]

\(y_1 = 1\)

\(y_2 = 6 - 3(1) = 3\)

\(y_3 = 0 - (-1)(1) = 1\)

\(y_4 = 3 - (-3)(1) - 4(3) - (-2)(1) = 3 + 3 - 12 + 2 = -4\)

Шаг 2. Решите \(U\mathbf{x} = \mathbf{y}\) обратной подстановкой. \[\begin{bmatrix} 1 & -2 & -2 & -3 \\ 0 & -3 & 6 & 0 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 1 \\ -4 \end{bmatrix}\]

\(x_4 = \frac{-4}{1} = -4\)

\(x_3 = \frac{1 - 4(-4)}{2} = \frac{17}{2}\)

\(x_2 = \frac{3 - 6(\frac{17}{2})}{-3} = \frac{3 - 51}{-3} = 16\)

\(x_1 = \frac{1 - (-2)(16) - (-2)(\frac{17}{2}) - (-3)(-4)}{1} = \frac{1 + 32 + 17 - 12}{1} = 38\)

Ответ: \(\mathbf{x} = \begin{bmatrix} 38 \\ 16 \\ \frac{17}{2} \\ -4 \end{bmatrix}\)

4.12. Умножение матриц и построчная интерпретация (Туториал 2, Задание 1)

Умножение матриц можно понимать через линейные комбинации. Покажите, что каждая строка произведения \(AB\) — линейная комбинация строк \(B\).

\(A = \begin{bmatrix} 2 & 1 & 4 \\ 0 & -1 & 1 \end{bmatrix}\), \(B = \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{bmatrix}\)

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Вычислите \(AB\). \[AB = \begin{bmatrix} 2 & 1 & 4 \\ 0 & -1 & 1 \end{bmatrix}_{2 \times 3} \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{bmatrix}_{3 \times 2} = \begin{bmatrix} 2(1) + 1(0) + 4(1) & 2(1) + 1(1) + 4(0) \\ 0(1) + (-1)(0) + 1(1) & 0(1) + (-1)(1) + 1(0) \end{bmatrix}\]

\[= \begin{bmatrix} 6 & 3 \\ 1 & -1 \end{bmatrix}\]

Шаг 2. Первая строка как комбинация строк \(B\). \[\text{Row}_1(AB) = \begin{bmatrix} 6 & 3 \end{bmatrix} = 2 \begin{bmatrix} 1 & 1 \end{bmatrix} + 1 \begin{bmatrix} 0 & 1 \end{bmatrix} + 4 \begin{bmatrix} 1 & 0 \end{bmatrix}\]

\[= 2 \cdot \text{row}_1(B) + 1 \cdot \text{row}_2(B) + 4 \cdot \text{row}_3(B)\]

Шаг 3. Вторая строка как комбинация строк \(B\). \[\text{Row}_2(AB) = \begin{bmatrix} 1 & -1 \end{bmatrix} = 0 \begin{bmatrix} 1 & 1 \end{bmatrix} + (-1) \begin{bmatrix} 0 & 1 \end{bmatrix} + 1 \begin{bmatrix} 1 & 0 \end{bmatrix}\]

\[= 0 \cdot \text{row}_1(B) - 1 \cdot \text{row}_2(B) + 1 \cdot \text{row}_3(B)\]

Ответ: каждая строка \(AB\) — линейная комбинация строк \(B\) с коэффициентами из соответствующей строки \(A\).

4.13. Влияние элементарных матриц на строки и столбцы (Туториал 2, Задание 2)

Опишите строки \(EA\) и столбцы \(AE\), если \[E = \begin{bmatrix} 1 & 7 \\ 0 & 1 \end{bmatrix}\]

Нажмите, чтобы увидеть решение

Решение:

Строки \(EA\):

При умножении \(E\) слева на \(A\) выполняются строковые операции над \(A\).

• 1-я строка \(EA = 1 \cdot (\text{1-я строка } A) + 7 \cdot (\text{2-я строка } A)\)
• 2-я строка \(EA = \text{2-я строка } A\)

Это прибавление кратной строки: новая 1-я строка = старая 1-я + \(7\times\) (2-я).

Столбцы \(AE\):

При умножении \(E\) справа на \(A\) выполняются столбцовые операции.

• 1-й столбец \(AE = \text{1-й столбец } A\)
• 2-й столбец \(AE = 7 \cdot (\text{1-й столбец } A) + 1 \cdot (\text{2-й столбец } A)\)

Ответ: слева \(E\) меняет строки (1-я становится 1-й + $7$2-я); справа — столбцы (2-й становится $7$1-й + 2-й).

4.14. Элементарные матрицы и произведения матриц (Туториал 2, Задание 3)

Запишите матрицы \(3 \times 3\), реализующие шаги исключения: a) \(E_{21}\) вычитает \(5\) раз строку 1 из строки 2. b) \(E_{32}\) вычитает \(-7\) раз строку 2 из строки 3.

Затем вычислите: (i) \(E_{32}E_{21}b\) и (ii) \(E_{21}E_{32}b\) для \(b = (1, 0, 0)^T\).

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Элементарные матрицы.

\[E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \quad E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 7 & 1 \end{bmatrix}\]

Шаг 2. \(E_{32}E_{21}b\).

\[E_{32}E_{21}b = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 7 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ -35 & 7 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ -5 \\ -35 \end{bmatrix}\]

Шаг 3. \(E_{21}E_{32}b\).

\[E_{21}E_{32}b = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 7 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 7 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ -5 \\ 0 \end{bmatrix}\]

Ответ:

• \(E_{32}E_{21}b = \begin{bmatrix} 1 \\ -5 \\ -35 \end{bmatrix}\) (3-я строка «чувствует» 1-ю через цепочку)
• \(E_{21}E_{32}b = \begin{bmatrix} 1 \\ -5 \\ 0 \end{bmatrix}\) (порядок другой — эффект на 3-ю строку иной)

4.15. LU-разложение исключением (часть a) (Туториал 2, Задание 4a)

Исключением получите множители \(L\) и \(U\) для \[ A = \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Гаусс до верхнетреугольного \(U\). \[\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix} \xrightarrow{R_2 : R_2 - 4R_1} \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix} = U\]

Шаг 2. \(E_{21}\) и \(L = E_{21}^{-1}\). \[E_{21} = \begin{bmatrix} 1 & 0 \\ -4 & 1 \end{bmatrix}, \quad L = E_{21}^{-1} = \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}\]

Ответ: \(L = \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}\), \(U = \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}\)

4.16. LU-разложение исключением (часть b) (Туториал 2, Задание 4b)

Исключением получите \(L\) и \(U\) для \[ A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 4 & 4 \\ 1 & 4 & 8 \end{bmatrix} \]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Приведение к \(U\). \[\begin{bmatrix} 1 & 1 & 1 \\ 1 & 4 & 4 \\ 1 & 4 & 8 \end{bmatrix} \xrightarrow{\substack{R_2 : R_2 - 1 \cdot R_1 \\ R_3 : R_3 - 1 \cdot R_1}} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 3 & 3 \\ 0 & 3 & 7 \end{bmatrix} \xrightarrow{R_3 : R_3 - 1 \cdot R_2} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 3 & 3 \\ 0 & 0 & 4 \end{bmatrix} = U\]

Шаг 2. \(L\) из обратных к шагам исключения. \[L = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}\]

Ответ: \(L = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}\), \(U = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 3 & 3 \\ 0 & 0 & 4 \end{bmatrix}\)

4.17. Условия невырожденности матрицы (часть a) (Туториал 2, Задание 5a)

При каких условиях следующее произведение невырождено (nonsingular)? \[A = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} d_1 & & \\ & d_2 & \\ & & d_3 \end{bmatrix} \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{bmatrix}\]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Структура \(A = LDU\):

• \(L = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix}\) (нижняя треугольная, на диагонали 1)
• \(D = \begin{bmatrix} d_1 & & \\ & d_2 & \\ & & d_3 \end{bmatrix}\) (диагональ)
• \(U = \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{bmatrix}\) (верхняя треугольная, на диагонали 1)

Шаг 2. \(\det(A) = \det(L)\det(D)\det(U) = d_1 d_2 d_3\).

Шаг 3. Невырожденность \(\Leftrightarrow\) \(\det(A) \neq 0\): \[d_1, d_2, d_3 \neq 0\]

Ответ: \(A\) невырождена тогда и только тогда, когда \(d_1, d_2, d_3 \neq 0\).

4.18. Решение системы с LDU-разложением (часть b) (Туториал 2, Задание 5b)

Решите систему \(Ax = b\), начиная с \(Lc = b\): \[\begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} = b\]

полное разложение: \(A = LDU\).

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Решите \(Lc = b\) относительно \(c\) прямой подстановкой. \[\begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\]

\(c_1 = 0\)

\(c_2 - c_1 = 0 \Rightarrow c_2 = 0\)

\(c_3 - c_2 = 1 \Rightarrow c_3 = 1\)

Шаг 2. Решите \(DUx = c\). \[\begin{bmatrix} d_1 & & \\ & d_2 & \\ & & d_3 \end{bmatrix} \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\]

Получаем: \[\begin{bmatrix} d_1(x_1 - x_2) \\ d_2(x_2 - x_3) \\ d_3 x_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\]

Шаг 3. Обратная подстановка.

\(d_3 x_3 = 1 \Rightarrow x_3 = \frac{1}{d_3}\)

\(d_2(x_2 - x_3) = 0 \Rightarrow x_2 = x_3 = \frac{1}{d_3}\)

\(d_1(x_1 - x_2) = 0 \Rightarrow x_1 = x_2 = \frac{1}{d_3}\)

Ответ: \(x = \frac{1}{d_3} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}\) (при \(d_1, d_2, d_3 \neq 0\))

4.19. Найти \(L\) и \(D\) по верхнетреугольной матрице (Туториал 2, Задание 6)

Каковы \(L\) и \(D\) в \(A = LDU\)? Чему равна верхняя \(U\) в \(A = LU\)? \[A = \begin{bmatrix} 2 & 4 & 8 \\ 0 & 3 & 9 \\ 0 & 0 & 7 \end{bmatrix}\]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. \(A\) уже верхнетреугольная с ненулевой диагональю \((2,3,7)\) — pivots на диагонали, исключение не нужно.

Шаг 2. В форме \(A = LDU\):

\[L = I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\]

\[D = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 7 \end{bmatrix}\]

\[U = D^{-1}A = \begin{bmatrix} 1 & 2 & 4 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{bmatrix}\]

Шаг 3. В записи \(A = LU\) (без отдельного \(D\)) верхний множитель — сама \(A\) при \(L = I\): \[A = LU = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 4 & 8 \\ 0 & 3 & 9 \\ 0 & 0 & 7 \end{bmatrix}\]

Ответ: \(L = I\), \(D = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 7 \end{bmatrix}\), \(U_{\text{unit}} = \begin{bmatrix} 1 & 2 & 4 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{bmatrix}\), \(U_{\text{for LU}} = \begin{bmatrix} 2 & 4 & 8 \\ 0 & 3 & 9 \\ 0 & 0 & 7 \end{bmatrix}\)

4.20. Связь между обратными матрицами (Туториал 2, Задание 7)

Если \((A^2)^{-1} = B\), докажите, что \(A^{-1} = AB\).

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Из условия \((A^2)^{-1} = B\) следует \(A^2 B = I\).

Шаг 2. Покажем, что \(AB\) — обратная к \(A\) справа.

Нужно \(A(AB) = I\). Так как \(A^2 = A \cdot A\), из \(A^2 B = I\): \[A(AB) = I\] то есть \(AB\) — правая обратная к \(A\).

Шаг 3. Для квадратной обратимой матрицы правая обратная совпадает с левой: из \(A(AB) = I\) также получается согласованность с \((BA)A = I\) при необходимости; для конечномерного случая \(AB = A^{-1}\).

Ответ: Из \(A^2 B = I\) имеем \(A(AB) = I\), значит \(AB = A^{-1}\).

4.21. Свойства, сохраняемые при обращении матрицы (Туториал 2, Задание 8)

Для обратимой \(A\) какие из свойств сохраняются у \(A^{-1}\)?

1. \(A\) треугольная → \(A^{-1}\) треугольная ✓

2. \(A\) симметрична → \(A^{-1}\) симметрична ✓

3. \(A\) трёхдиагональна → \(A^{-1}\) трёхдиагональна ✗

4. все элементы целые → у \(A^{-1}\) все элементы целые ✗

5. все элементы — дроби → у \(A^{-1}\) элементы — дроби ✓

Нажмите, чтобы увидеть решение

Решение:

(a) Треугольность

Если \(A\) верхнетреугольная, \(A = \begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix}\), \(A_{11}\) — \((n-1) \times (n-1)\) верхнетреугольная. По формуле для блочной обратной: \[A^{-1} = \begin{bmatrix} A_{11}^{-1} & -A_{11}^{-1}A_{12}A_{22}^{-1} \\ 0 & A_{22}^{-1} \end{bmatrix}\] Индукцией \(A_{11}^{-1}\) верхнетреугольна ⇒ \(A^{-1}\) верхнетреугольна. ✓

(b) Симметричность

Если \(A = A^T\), то \((A^{-1})^T = (A^T)^{-1} = A^{-1}\). ✓

(c) Трёхдиагональность

Контрпример: \[A = \begin{bmatrix} 1 & 1 & 0 \\ 2 & 1 & 2 \\ 0 & 3 & 1 \end{bmatrix}\] \[A^{-1} = \begin{bmatrix} 1.6087 & -0.3043 & -0.4348 \\ -0.6087 & 0.3043 & 0.4348 \\ -1.3043 & 0.6522 & 0.2174 \end{bmatrix}\] не трёхдиагональна. ✗

(d) Целые элементы

Контрпример: \[A = \begin{bmatrix} 1 & 1 & 1 & 4 \\ 2 & 1 & 2 & 7 \\ 3 & 3 & 1 & 3 \\ 9 & 3 & 4 & 5 \end{bmatrix}\] у \(A\) целые элементы, у \(A^{-1}\) — дробные. ✗

(e) Дробные элементы

Если все элементы \(A\) — дроби, то \(A = \frac{1}{d}\tilde{A}\) с целой \(\tilde{A}\) и общим знаменателем \(d\); \(A^{-1}\) выражается через деление и остаётся в классе рациональных элементов. ✓

Ответ: сохраняются (a), (b), (e); не сохраняются (c) и (d).

4.22. Условия обратимости треугольных матриц (часть a) (Туториал 2, Задание 9a)

При каких условиях на элементы следующая матрица обратима?

\[A = \begin{bmatrix} a & b & c \\ d & e & 0 \\ f & 0 & 0 \end{bmatrix}\]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Метод Гаусса–Жордана на \([A|I]\).

\[\left[\begin{array}{ccc|ccc} a & b & c & 1 & 0 & 0 \\ d & e & 0 & 0 & 1 & 0 \\ f & 0 & 0 & 0 & 0 & 1 \end{array}\right]\]

Шаг 2. Поменять строки 1 и 3, чтобы \(f\) стал первым опорным: \[\left[\begin{array}{ccc|ccc} f & 0 & 0 & 0 & 0 & 1 \\ d & e & 0 & 0 & 1 & 0 \\ a & b & c & 1 & 0 & 0 \end{array}\right]\] Нужно \(f \neq 0\).

Шаг 3. \(R_2 : R_2 - \frac{d}{f}R_1\), \(R_3 : R_3 - \frac{a}{f}R_1\): \[\left[\begin{array}{ccc|ccc} f & 0 & 0 & 0 & 0 & 1 \\ 0 & e & 0 & 0 & 1 & -d/f \\ 0 & b & c & 1 & 0 & -a/f \end{array}\right]\] Нужно \(e \neq 0\).

Шаг 4. \(R_3 : R_3 - \frac{b}{e}R_2\): \[\left[\begin{array}{ccc|ccc} f & 0 & 0 & 0 & 0 & 1 \\ 0 & e & 0 & 0 & 1 & -d/f \\ 0 & 0 & c & 1 & -b/e & -a/f + bd/ef \end{array}\right]\] Нужно \(c \neq 0\).

Ответ: \(A\) обратима тогда и только тогда, когда \(f \neq 0\), \(e \neq 0\) и \(c \neq 0\).

4.23. Условия обратимости блочно-диагональных матриц (Туториал 2, Задание 9b)

При каких условиях на элементы матрица обратима?

\[B = \begin{bmatrix} a & b & 0 \\ c & d & 0 \\ 0 & 0 & e \end{bmatrix}\]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Блочно-диагональный вид: \[B = \begin{bmatrix} M & 0 \\ 0 & e \end{bmatrix}, \quad M = \begin{bmatrix} a & b \\ c & d \end{bmatrix}.\]

Шаг 2. \(\det(B) = \det(M) \cdot e = (ad - bc) \cdot e\).

Шаг 3. Обратимость ⇔ \(\det(B) \neq 0\): \[(ad - bc) \cdot e \neq 0\] то есть \(ad - bc \neq 0\) и \(e \neq 0\).

Ответ: \(B\) обратима тогда и только тогда, когда \(ad - bc \neq 0\) и \(e \neq 0\).

4.24. Вычисление обратных для матриц \(2 \times 2\) (Туториал 2, Задание 10)

Найдите обратные (напрямую или по формуле для \(2 \times 2\)) к

\(A = \begin{bmatrix} 0 & 3 \\ 4 & 6 \end{bmatrix}\), \(B = \begin{bmatrix} a & b \\ b & 0 \end{bmatrix}\), \(C = \begin{bmatrix} 3 & 4 \\ 5 & 7 \end{bmatrix}\)

Нажмите, чтобы увидеть решение

Решение:

Формула для \(2 \times 2\): \[\begin{bmatrix} a & b \\ c & d \end{bmatrix}^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\]

Матрица \(A\):

\[\det(A) = 0 \cdot 6 - 3 \cdot 4 = -12\]

\[A^{-1} = \frac{1}{-12} \begin{bmatrix} 6 & -3 \\ -4 & 0 \end{bmatrix} = \begin{bmatrix} -1/2 & 1/4 \\ 1/3 & 0 \end{bmatrix}\]

Матрица \(B\):

\[\det(B) = a \cdot 0 - b \cdot b = -b^2\]

\[B^{-1} = \frac{1}{-b^2} \begin{bmatrix} 0 & -b \\ -b & a \end{bmatrix} = \begin{bmatrix} 0 & 1/b \\ 1/b & -a/b^2 \end{bmatrix}\]

(при \(b \neq 0\))

Матрица \(C\):

\[\det(C) = 3 \cdot 7 - 4 \cdot 5 = 21 - 20 = 1\]

\[C^{-1} = \frac{1}{1} \begin{bmatrix} 7 & -4 \\ -5 & 3 \end{bmatrix} = \begin{bmatrix} 7 & -4 \\ -5 & 3 \end{bmatrix}\]

Ответ:

• \(A^{-1} = \begin{bmatrix} -1/2 & 1/4 \\ 1/3 & 0 \end{bmatrix}\)
• \(B^{-1} = \begin{bmatrix} 0 & 1/b \\ 1/b & -a/b^2 \end{bmatrix}\) (при \(b \neq 0\))
• \(C^{-1} = \begin{bmatrix} 7 & -4 \\ -5 & 3 \end{bmatrix}\)

4.25. Обратная матрица методом Гаусса–Жордана (Туториал 2, Задание 11)

Найдите \(A^{-1}\) методом Гаусса–Жордана, начиная с \([A|I]\): \[A = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 3 \\ 0 & 0 & 1 \end{bmatrix}\]

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Расширенная матрица \([A|I]\). \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 2 & 1 & 3 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{array}\right]\]

Шаг 2. \(R_2 : R_2 - 2R_1\): \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 3 & -2 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{array}\right]\]

Шаг 3. \(R_2 : R_2 - 3R_3\): \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & -2 & 1 & -3 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{array}\right]\]

Ответ: \(A^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & -3 \\ 0 & 0 & 1 \end{bmatrix}\)

4.26. Степени матрицы и общая закономерность (часть a) (Туториал 2, Задание 12a)

По опыту для \(n = 2\) и \(n = 3\) найдите \(\begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix}^n\).

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Квадрат: \[\begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix}^2 = \begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 4 & 6 \\ 0 & 0 \end{bmatrix}\]

Шаг 2. Куб: \[\begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix}^3 = \begin{bmatrix} 4 & 6 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 8 & 12 \\ 0 & 0 \end{bmatrix}\]

Шаг 3. Закономерность при \(n \geq 1\): \[\begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix}^n = \begin{bmatrix} 2^n & 3 \cdot 2^{n-1} \\ 0 & 0 \end{bmatrix}\]

Ответ: \(\begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix}^n = \begin{bmatrix} 2^n & 3 \cdot 2^{n-1} \\ 0 & 0 \end{bmatrix}\)

4.27. Степени матрицы и перестановочность (часть b) (Туториал 2, Задание 12b)

По опыту для \(n = 2\) и \(n = 3\) найдите \(\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^n\).

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Квадрат: \[\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^2 = \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 4 & 9 \\ 0 & 1 \end{bmatrix}\]

Шаг 2. Куб: \[\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^3 = \begin{bmatrix} 4 & 9 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 8 & 21 \\ 0 & 1 \end{bmatrix}\]

Шаг 3. При \(n \geq 1\): \[\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 2^n & 3(2^{n-1} + 2^{n-2} + \cdots + 2 + 1) \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2^n & 3(2^n - 1) \\ 0 & 1 \end{bmatrix}\]

Ответ: \(\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 2^n & 3(2^n - 1) \\ 0 & 1 \end{bmatrix}\)

4.28. Обратная матрица через Гаусса–Жордана (часть c) (Туториал 2, Задание 12c)

Найдите \(\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^{-1}\) методом Гаусса–Жордана.

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. \[\left[\begin{array}{cc|cc} 2 & 3 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array}\right]\]

Шаг 2. \(R_1 : R_1 - 3R_2\): \[\left[\begin{array}{cc|cc} 2 & 0 & 1 & -3 \\ 0 & 1 & 0 & 1 \end{array}\right]\]

Шаг 3. \(R_1 : R_1/2\): \[\left[\begin{array}{cc|cc} 1 & 0 & 1/2 & -3/2 \\ 0 & 1 & 0 & 1 \end{array}\right]\]

Ответ: \(\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1/2 & -3/2 \\ 0 & 1 \end{bmatrix}\)

4.29. Общая закономерность для элементарных нижнетреугольных матриц (часть a) (Туториал 2, Задание 13a)

По опыту или методу Гаусса–Жордана найдите \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^n\).

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. Квадрат: \[\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^2 = \begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 2l & 1 & 0 \\ 2m & 0 & 1 \end{bmatrix}\]

Шаг 2. Куб: \[\begin{bmatrix} 1 & 0 & 0 \\ 2l & 1 & 0 \\ 2m & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 3l & 1 & 0 \\ 3m & 0 & 1 \end{bmatrix}\]

Шаг 3. Общий вид: \[\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 1 & 0 & 0 \\ nl & 1 & 0 \\ nm & 0 & 1 \end{bmatrix}\]

Ответ: \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 1 & 0 & 0 \\ nl & 1 & 0 \\ nm & 0 & 1 \end{bmatrix}\)

4.30. Обратная к элементарной нижнетреугольной матрице (часть b) (Туториал 2, Задание 13b)

Найдите \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^{-1}\).

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. По закономерности из (a): \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 1 & 0 & 0 \\ nl & 1 & 0 \\ nm & 0 & 1 \end{bmatrix}\); подставим \(n = -1\): \[\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ -l & 1 & 0 \\ -m & 0 & 1 \end{bmatrix}\]

Шаг 2. Проверка умножением: \[\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -l & 1 & 0 \\ -m & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\] ✓

Ответ: \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ -l & 1 & 0 \\ -m & 0 & 1 \end{bmatrix}\)

4.31. Обратная к модифицированной нижнетреугольной матрице (часть c) (Туториал 2, Задание 13c)

Найдите \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ 0 & m & 1 \end{bmatrix}^{-1}\) методом Гаусса–Жордана.

Нажмите, чтобы увидеть решение

Решение:

Шаг 1. \([A|I]\): \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ l & 1 & 0 & 0 & 1 & 0 \\ 0 & m & 1 & 0 & 0 & 1 \end{array}\right]\]

Шаг 2. \(R_2 : R_2 - lR_1\): \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & -l & 1 & 0 \\ 0 & m & 1 & 0 & 0 & 1 \end{array}\right]\]

Шаг 3. \(R_3 : R_3 - mR_2\): \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & -l & 1 & 0 \\ 0 & 0 & 1 & ml & -m & 1 \end{array}\right]\]

Ответ: \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ 0 & m & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ -l & 1 & 0 \\ ml & -m & 1 \end{bmatrix}\)